"""
堆排序-----topk问题
    - 现在有n个数，设计算法得到前K大的数。（K<n）
    - 解决方法
        - 排序后切片    O(nlogn)
        - 排序LowB三人组   O(kn)
        - 堆排序思路       O(nlogk)
            - 解决思路：
                - 取列表前K个元素建立一个小要堆。堆顶就是目前第K大的数
                - 依次向后遍历原列表, 对于列表中的元素, 如果小于堆顶, 则忽略该元素；
                  如果大于堆顶, 则将堆顶更换为该元素, 并且对堆进行一次调整
"""

from SortingAlgorithm.cal_time.cal_time import cal_time


def sift(li, low, high):
    """
    这个调整的过程时间复杂度为：O(logn)
    :param li: 列表
    :param low: 堆的根节点位置
    :param high: 堆的最后一个元素的位置
    """
    i = low        # i最开始指向根节点
    j = 2 * i + 1  # j开始是左孩子
    tmp = li[low]  # 把堆顶存起来
    while j <= high:
        if j + 1 <= high and li[j+1] < li[j]:  # 如果右孩子有并且比左孩子小
            j = j + 1  # j指向右孩子
        if li[j] < tmp:
            li[i] = li[j]
            i = j      # 往下一层来进行调整
            j = 2 * i + 1
        else:          # tmp小,把tmp放到i的位置上
            li[i] = tmp   # 把tmp放到某一级领导位置上
            break
    else:
        li[i] = tmp   # 把tmp放到叶子节点上


def topk(li, k):
    heap = li[0:k]
    # 建堆
    for i in range((k-2)//2, -1, -1):
        sift(heap, i, k-1)

    # 遍历
    for i in range(k, len(li)-1):
        if li[i] > heap[0]:
            heap[0] = li[i]
            sift(heap, 0, k-1)

    # 出数
    for i in range(k-1, -1, -1):
        heap[0], heap[i] = heap[i], heap[0]
        sift(heap, 0, i-1)

    return heap

li = [i for i in range(1000)]
import random
random.shuffle(li)
# print(li)

print(topk(li, 10))